package com.mystudy.leetcode.problem.array.p_303;

/**
 * @program: infoalgorithm
 * @description: 区域和检索 - 数组不可变
 * @author: zhouzhilong
 * @create: 2019-08-07 13:44
 **/
public class NumArray {

    private int[] tree;
    private int[] data;

    public NumArray(int[] nums) {
        if(nums==null || nums.length <=0){
            return;
        }
        this.data = nums;
        tree = new int[nums.length * 4];
        buildSegmentTree(0, 0, nums.length - 1);
    }

    /**
     * 在rootIndex节点开始构建一棵线段树
     *
     * @param rootIndex
     * @param l
     * @param r
     */
    private void buildSegmentTree(int rootIndex, int l, int r) {
        if (l == r) {
            tree[rootIndex] = data[l];
            return;
        }

        int mid = (l + r) / 2;
        int leftChild = leftChild(rootIndex);
        int rightChild = rightChild(rootIndex);
        buildSegmentTree(leftChild, l, mid);
        buildSegmentTree(rightChild, mid + 1, r);
        tree[rootIndex] = tree[leftChild] + tree[rightChild];
    }

    private int leftChild(int rootIndex) {
        return rootIndex * 2 + 1;
    }

    private int rightChild(int rootIndex) {
        return rootIndex * 2 + 2;
    }


    public int sumRange(int i, int j) {
        return sum(0, 0, data.length - 1, i, j);
    }

    private int sum(int rootIndex, int l, int r, int queryL, int queryR) {
        if(l == queryL && r == queryR){
            return tree[rootIndex];
        }
        int mid = (r + l) / 2;
        int leftChild = leftChild(rootIndex);
        int rightChild = rightChild(rootIndex);

        if (queryL >= mid+1) {
            //说明要查询的范围不在左子树
            return sum(rightChild,mid+1,r,queryL,queryR);
        }else if(queryR <= mid){
            //说明要查询的范围不在右子树
            return sum(leftChild,l,mid,queryL,queryR);
        }

        int leftResult = sum(leftChild, l, mid, queryL, mid);
        int rightResult = sum(rightChild, mid + 1, r, mid+1, queryR);
        return leftResult+rightResult;

    }


    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append('[');
        for (int i = 0; i < tree.length; i++) {
                res.append(tree[i]);

            if(i != tree.length-1){
                res.append(",");
            }
        }
        return res.toString();
    }
}
